<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>Maxmilite</title>
    <link rel="icon" href="../icon.png" type="image/x-icon">
</head>

<link rel="stylesheet" href="../css/style-archive.css">

<canvas id="snow-flake-app"></canvas>
<script src="../js/snow-flake-app.js"></script>

<!-- <ul class="nav">
    <li style="width: 40%;">
        <div>
            <p style="font-size: xx-large;"><img src="../icon.png" height="40px" width="40px"
                    style="border-radius: 4px;">&nbsp;Maxmilite</p>
        </div>
    </li>
</ul> -->

<div class="main">
    <h1 style="text-align: center;">
        题解 AT4284 【[ABC116C] Grand Garden】
    </h1>
</div>

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});
</script>
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<xmp theme="united" style="display:none;" id="section">
### 题意描述：

花床上有 $N$ 枝花，每次可以选定一个连续区间让这个区间里的花高度 $+1$，求至少需要多少次操作才可以让花的高度长到给定序列那样

### 4.5 倍经验：
[P3078](https://www.luogu.com.cn/problem/P3078) 完全一致

[P1969](https://www.luogu.com.cn/problem/P1969) 完全一致

[P5019](https://www.luogu.com.cn/problem/P5019) 完全一致

[AT4284(本题)](https://www.luogu.com.cn/problem/AT4284) 完全一致

[CF448C](https://www.luogu.com.cn/problem/CF448C) 极其相似

### 解法

核心要点：**贪，都可以贪**

贪心做法，从前往后遍历，每当找到一个 $h_{i} > h_{i - 1}$ 操作次数就加上 $h_{i} -  h_{i - 1}$

### 为什么这样解

可以理解为当找到一个高点 （即 $h_{i} > h_{i - 1}$），那就可以顺便把他后面递减的区间一起干掉。由于区间保证递减  （即 $h_{i} \leq h_{i - 1}$），所以可以保证像金字塔那样，每次操作的区间都是连续的。

![](https://cdn.luogu.com.cn/upload/image_hosting/mrao9sgg.png)

（黑色框表示每个点需求的高度，红色框表示操作顺序）

如果遇到操作区间内（即 $h_{i} > h_{i - 1}$），那么就会出现这种状况

![](https://cdn.luogu.com.cn/upload/image_hosting/lduf0pdh.png)

（断档了）

### AC Code:

```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    long long n, a, last(0), ans(0);
    cin >> n;
    for (long long i = 1; i <= n; ++i)
    {
        cin >> a;
        ans += a > last ? (a - last) : 0;
        last = a;
    }
    cout << ans << endl;
    return 0;
}
```
</xmp>


<script src="strapdown/v/0.2/strapdown.js"></script>

<div>
    <!-- Button Here -->
    <!-- Fixed Button 2021-04-18-->
    <a class="button" href="../archives.html" style="width: 40%; border-radius: 8px; margin-left: 30%; margin-top: 100px;  margin-bottom: 40px">
        <p style="font-size: 2vmax;">
            <<< Return to archive list </p>
    </a>
</div>

</html>